class Solution {
    public int countSubstrings(String s) {
        int ans = 0;

        int len = s.length();
        boolean[][] d = new boolean[len][len];
        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                char ch1 = s.charAt(i);
                char ch2 = s.charAt(j);
                if (i == j) {
                    d[i][j] = true;
                } else if ( j - i == 1 && ch1 == ch2) {
                    d[i][j] = true;
                } else if (d[i + 1][j - 1] && ch1 == ch2) {
                    d[i][j] = true;
                }

                if (d[i][j])
                    ans++;
            }
        }
        // for (boolean[] ints : d) {
        //     System.out.println(Arrays.toString(ints));
        // }
        return ans;
    }
}